package com.stanley.alogrithm.dynamic_divider;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 长度为n的钢材，如何切割销售，收益最大？
 */
public class BestCut {


    public static void main(String[] args) {
        int[] prices = {1, 5, 8, 9, 10, 17, 17, 20, 24, 30};

        int n = 8;
        BestCut bestCut = new BestCut();
        ArrayList<Integer> cuts = new ArrayList<>();
        long start = System.nanoTime();
        //int v = bestCut.bestCut(n, prices, cuts);\
        int[] solutions = new int[n];
        int v = bestCut.bottomUpCut(n, prices, solutions);
        long cost = System.nanoTime() - start;
        System.out.println("Result: " + v + ", costTime=" + cost + ", solutions: " + Arrays.toString(solutions));
//        solutions.stream().forEach(s -> {
//            System.out.print(s + ",");
//        });

    }


    public int bestCut(int n, int[] prices, ArrayList<Integer> solutionList) {
        int[] records = new int[n];

        return calcCut(n, records, prices, solutionList);
    }


    private int calcCut(int n, int[] r, int[] prices, List<Integer> solution) {
        if (n == 0) {
            return 0;
        }

        if (r[n - 1] > 0) {
            solution.add(n);
            return r[n - 1];
        }

        int q = 0;
        int bestI = 0;
        List<Integer> bestS = null;
        List<Integer> tempS = null;
        for (int i = 1; i <= n; i++) {
            tempS = new ArrayList<>();
            int x = prices[i - 1] + calcCut(n - i, r, prices, tempS);
            if (q < x) {
                q = x;
                bestI = i;
                bestS = tempS;
            }
        }
        r[n - 1] = q;
        solution.add(bestI);
        solution.addAll(bestS);
        return q;
    }

    private int bottomUpCut(int n, int[] prices, int[] solutions) {
        int[] records = new int[n];
        int[] firstCuts = new int[n];
        int q = 0;
        for (int j = 1; j <= n; j++) {
            q = 0;
            for (int i = 1; i <= j; i++) {
                int r = i == j ? 0 : records[j - i - 1];
                int p = prices[i - 1] + r;
                if (p > q) {
                    q = p;
                    firstCuts[j - 1] = i;
                }
            }
            records[j - 1] = q;
        }
        int s = 0;
        int l = n;
        while (l > 0) {
            solutions[s++] = firstCuts[l - 1];
            l = l - firstCuts[l - 1];
        }
        return q;
    }
}
